package JavaEE_Advance;

import java.util.*;

public class Day01 {

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        if (k <= 0 || n < k) {
            return res;
        }
        // 从 1 开始是题目的设定
        Deque<Integer> path = new ArrayDeque<>();
        dfs(n, k, 1, path, res);
        return res;
    }

    private static void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        // 递归终止条件是：path 的长度等于 k
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 遍历可能的搜索起点
        for (int i = begin; i <= n; i++) {
            // 向路径变量里添加一个数
            path.addLast(i);
            // 下一轮搜索，设置的搜索起点要加 1，因为组合数理不允许出现重复的元素
            dfs(n, k, i + 1, path, res);
            // 重点理解这里：深度优先遍历有回头的过程，因此递归之前做了什么，递归之后需要做相同操作的逆向操作
            path.removeLast();
        }
    }


    public static void main(String[] args) {
//        System.out.println(subsets(new int[]{1, 2, 3}));
//        System.out.println(combine2(4, 2));
        combine(4, 2);
    }

    // https://leetcode.cn/problems/combinations/
    // 方法1 先筛选出全部在过滤 -- 时间会超出
    public static List<List<Integer>> combine2(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        List<List<Integer>> list = subsets(nums).stream().filter((e) -> e.size() == k).toList();
        return list;
    }


    // https://leetcode.cn/problems/subsets/solutions/420294/zi-ji-by-leetcode-solution/
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new LinkedList<>();
        recursion(nums, 0, list);
        return list;
    }

    // 采用递归的方法
    private static void recursion(int[] nums, int index , List<List<Integer>> list) {
        if (index == nums.length && index != 0) {
            // 添加空
            list.add(new LinkedList<>());
            return;
        }
        int len = list.size(); // 不能将len替换 不然会陷入死循环
        for (int i = 0; i < len; i++) {
            List<Integer> tmp = list.get(i);
            List<Integer> copy = new ArrayList<>(tmp);
            copy.add(nums[index]);
            list.add(copy);
        }
        // 添加本体
        list.add(List.of(nums[index]));
        recursion(nums, index + 1 ,list);
    }
}
